A Hybrid Adjacency and Time-Based Data Structure for Analysis of Temporal Networks
- Project Research
- 1-5 Chapters
- Abstract : Available
- Table of Content: Available
- Reference Style: APA
- Recommended for : Student Researchers
- NGN 3000
Background
Related Work I begin with background information on ways for representing temporal networks and data structures for storing (static) networks. I then discuss work related to this thesis, including the use of hybrid data structures and other types of temporal network data structures. 2.1 Static Network Representations Static networks are typically represented in one of 3 ways [41]: • Adjacency matrix : A two-dimensional matrix, Auv, stores edge information for source node u to destination node v in the uvth element of the matrix. • Adjacency list: A set of lists, one for each source node u. Each list contains a series of destination nodes v, if edge (u, v) exists. • Adjacency dictionary: A hash table keyed by source nodes u mapped to the set of destination nodes v, if edge (u, v) exists. The adjacency matrix is the traditional data structure for network representation due to, in part, its simple construction, but also its prominence in key aspects of network analysis, such as spectral graph theory. The values stored in adjacency 7 matrices are typically boolean in nature, with a value of ”1” representing an edge is present between two nodes, and a value of ”0” otherwise. However, adjacency matrices can be modified to hold additional information by storing numeric values instead, e.g. edge weights. Since an adjacency matrix stores a value for both present and missing edges, it has a memory complexity of O(n 2 ), where n is the number of nodes, and is therefore only appropriate for smaller networks. The adjacency list representation aims to improve upon this memory complexity by removing the need to store missing edge information. By storing edges as a set of list, adjacency lists improve the memory complexity to O(k), where k is the number of edges. However, this approach suffers from increased time complexity during common operations such as finding if an edge exists between nodes u and v due to the unsorted nature of its lists. The adjacency dictionary representation is a variant on the standard adjacency list, by storing the edges in a hashed set rather than a list. Edges presence in an adjacency dictionary can be determined in O(1) time, matching the adjacency matrix, while retaining the O(k) space complexity of the adjacency list. By using a hash table instead of a hashed set, additional edge information can be stored inside the adjacency dictionary as well.
Related Project Materials
ASSESSMENT OF RESOURCE MANAGEMENT IN GOVERNMENT SECONDARY SCHOOLS IN THE FEDERAL CAPITAL TERRITORY (FCT) ABUJA, NIGERIA
ABSTRACT
The study examined the Management of Resources in FCT Government Secondary Schools Abuja, Nigeria. The objectives of the study a...
CONSUMERS’ PERCEPTION OF TRUTH IN ADVERTISING
ABSTRACT
This research study surveys how certain advertising strategies affect consumers’ perception of truth in them with outcomes...
THE ROLE OF EARLY CHILDHOOD EDUCATION IN FOSTERING INTERGENERATIONAL RELATIONSHIPS
ABSTRACT: The role of early childhood education in fostering interge...
THE PROBLEM OF TEACHING AND LEARNING ACCOUNTING IN NIGERIA UNIVERSITIES
OVERVIEW OF THE STUDY
Accounting as one of the subjects in business education, has functions of developing in individuals,...
RAINFALL PREDICTION FOR MINNA METROPOLIS USING ARTIFICIAL NEURAL NETWORK
ABSTRACT
The effect of rainfall in our society today is stupendous. Rainfall is seen as a benefit to crops and lives. Accurate and timely...
DESIGN AND IMPLEMENTATION OF AN COMPUTERISED COOPERATIVE SOCIETY
ABSTRACT
The proposed project topic above is centered on the critical needed for registration of both the individuals an...
IMPACT OF AUDIO VISUAL AIDS IN TEACHING HOME ECONOMICS IN SECONDARY SCHOOLS
Teaching and learning activities are interesting when instructional materials are used effectively and efficiently in a classroom-teaching situatio...
THE IMPLEMENTATION OF PROGRESSIVISM IN NIGERIAN EDUCATION: AN ASSESSMENT
ABSTRACT
The thesis sought to assess the extent to which progressive education is implemented in Nigeria. This is essentially because whi...
THE PROBLEMS OF CLASSROOM MANAGEMENT AND CONTROL IN SECONDARY SCHOOL
Background to the Study
The idea behind discipline in school is not across a single point of view About the proper defin...
PATHOGENICITY of Heterodera sacchari (LUC AND MERNY) AND ITS INTERACTION WITH Botryodiplodia theobromae (PAT) ON SOME NERICA RICE CULTIVARS
ABSTRACT
The Cyst Nematode (CN), Heterodera sacchari, is an important pest that causes yield losses of upland rice. NERICA Rice (NR) is a...
